The present invention relates to an ATM cell spacer.
A general description of this kind of facility can be found in the article by P. E. BOYER et al.: xe2x80x9cSpacing Cells Protects and Enhances Utilization of ATM Network Linksxe2x80x9d (IEEE Network, September 1992, pages 38-49).
ATM cells are 53-byte information packets transmitted over high-speed physical links (bit rate of 155 or 622 Mbit/s). Each physical link supports a multiplex of cells belonging to various virtual connections. The virtual connection to which each cell pertains is identified by a pair of identifiers VPI-VCI contained in the header of the cell. Certain facilities differentiate between virtual connections according to the virtual path identifier (VPI), while other facilities differentiate between the virtual connections on the basis of the virtual channel identifiers (VCI), or of both identifiers VPI, VCI.
In the present description, each ATM call will be regarded as pertaining to a virtual connection identified by an identity IdCx internal to the facility provided with the spacer. This internal identity can correspond to the VPI, to the VCI, to the pair VPI-VCI, or else, more conveniently, to a specific identity individual to the facility and comprising a smaller number of bits than the VPI-VCI, so as to facilitate accesses to memory modules of reasonable size. An appropriate way of associating such identities IdCx with the ATM cells is described in French Patent Application No. 97 01222.
The ATM spacer is a unit whose main function is to regularize the bit rate of cells over the various connections supported by a physical link. In general, each source emitting on a virtual connection negotiates a peak bit rate with the operator. If this peak bit rate is not complied with by the source, there is a risk of congestions occurring in the network, and the operator is empowered to destroy cells on the connection.
In a spacer, a spacing interval T is allotted to each connection IdCx, in such a way that two consecutive cells relating to the same virtual connection are generally separated by at least the time interval T which typically corresponds to the inverse of the peak bit rate. We then speak of a real spacer. The real spacer calculates a theoretical emission time TET for each cell and then stores the cell in memory so as to emit it only at the desired time. The spacing interval T is then complied with for all the connections. In a so-called virtual spacer, a theoretical emission time TET is firstly calculated for each cell according to the same methods as before, and then the cell is stored in memory. The difference with the real spacer is that the virtual spacer emits the cells immediately in the order of the theoretical emission times. The virtual spacer does not degrade the cell delay variation (CDV). However, it does not allay the possible degradation of the bit rate by queues located upstream of the spacer.
The spacing function is frequently associated with the policing function which consists in eliminating cells transmitted in accordance with a virtual connection at a bit rate greater than the peak bit rate, when this excess bit rate is such that it is no longer possible to produce an output multiplex in which the cells pertaining to the connection are correctly spaced without the CDV exceeding a limit value depending on the quality of service negotiated with the operator. The policing function usually enters into the way of calculating the theoretical emission times TET of the cells.
A conventional way of allotting theoretical emission times to the cells and of performing the policing function is to apply the GCRA algorithm (xe2x80x9cGeneric Cell Rate Algorithmxe2x80x9d) defined in Annex 1 of ITU-T Recommendation I.371 (see M. DE PRYCKER: xe2x80x9cAsynchronous Transfer Mode, Solution for Broadband ISDNxe2x80x9d, 2nd Edition, 1993, Chapter 7, paragraph 7.3.4, pages 292-293). For each virtual connection, this algorithm always satisfies the following relation: taxe2x89xa6TETxe2x89xa6ta+xcfx84, where ta denotes the time of arrival of the cell, at which its theoretical emission time TET is calculated, and xcfx84 denotes the CDV tolerance of the connection.
Cells pertaining to different virtual connections may find themselves allotted the same theoretical emission time. As a result it is necessary to provide a mechanism for resolving such conflicts.
A first solution, described in the document EP-A-0 438 009, consists in storing each incoming cell at an address of the cell memory corresponding to its actual time of emission. At the output of the spacer, a time counter serves as address pointer for designating the cells to be emitted. After assigning a theoretical emission time to the cell, the latter is stored at the first available address after this theoretical time, thereby avoiding conflicts.
A second solution, described in the document EP-A-0 498 092 (see also E. Wallmeier et al.: xe2x80x9cThe Spacing Policer, an Algorithm for Efficient Peak Bit Rate Control in ATM Networksxe2x80x9d, Proc. of ISS""92, October 1992, Vol. 2, pages 22-26), consists in associating, with each emission period, a list of cells chained by means of pointers. When an emission period is reached, the cells of the associated list are read and output one by one during this period and during the required number of succeeding periods.
A third solution, described in the article xe2x80x9cA Real Time Sorter with Application to ATM Traffic Controlxe2x80x9d by J. W. Roberts et al. (Proc. of ISS""95, April 1995, Vol. 1, pages 258-262), consists in utilizing a sorting technique: with the arrival of each cell, a data element made up of the cell storage address and of a sort key corresponding to its theoretical emission time is introduced into a sorting device, which at each emission period produces an element, having a minimum sort key. The cell whose address is contained in this element is emitted if the minimum key is less than or equal to the current time in the case of a real spacer, or immediately in the case of a virtual spacer. The sorting device must be capable of sorting a number N of elements equal to the maximum number of cells stored in the spacer. Moreover, it is noted that the sorting device advocated has the drawback that the number of logic circuits operating in parallel so as to perform the sorting function at a sufficient rate is proportional to N. Once the number N of elements to be sorted becomes large (a few thousand or tens of thousands as in the case of the application to an ATM cell spacer), the hardware complexity of the sorting device becomes prohibitive.
In the three solutions above, the spacer ignores the concept of virtual connection once a theoretical emission time has been allotted to an incoming cell. As a result, the procedure for determining a stored cell to be emitted is the choosing of a cell from a number corresponding to the maximum storage capacity of the spacer. This implies superfluous complexity from the moment that in principle the order of reception of the cells pertaining to one and the same virtual connection must be complied with on emission.
Should there be a risk of traffic congestion on the link equipped with the spacer, the operator sometimes has the option of increasing the spacing intervals T allotted to certain connections. However, such a modification of T acts only on the cells which have not yet been received, and not on those already written to the buffer memory of the spacer, given that the theoretical emission times calculated previously are no longer modifiable without knowing the connections concerned; yet, a sufficient number of cells may already have been written to the buffer memory for the increase in the intervals T to be ineffective in preventing congestion. The above spacers lack flexibility in this respect.
An ATM spacer, in which the selecting of the cell to be emitted is effected on the basis of the theoretical emission times assigned to the cells stored in the starts of FIFO lists allotted to the various virtual connections, is described in EP-A-0 710 046. This document describes a particular method of calculating the emission times in accordance with which the theoretical time of emission of a cell depends on the actual time of emission of the preceding cell pertaining to the same virtual connection. A similar method is described in the article xe2x80x9cMultiplexing Spacer Outputs on Cell Emissionsxe2x80x9d, by G. Mercankosk et al., Proc. Infocom""95xe2x80x94Conference on Computer Communications, 14th Annual Joint Conference of the IEEE Computer and Communications Societies, Boston, Apr. 2-6 1995, Vol. 3, pages 49-55.
This type of method has the drawback that, when a cell is delayed because of a conflict between cells pertaining to different connections and to which the same theoretical emission time has been allotted, the succeeding cells of the same connection are also delayed even if the conflict has disappeared. Such cases result in needless disturbance to the flow.
An object of the present invention is to propose an ATM spacer which is less affected by the above drawbacks.
The invention thus proposes a spacer of ATM cells transmitted according to a plurality of virtual connections, comprising:
a cell memory to which incoming cells are written and from which outgoing cells are read;
means for allocating a theoretical emission time to each cell stored in the cell memory, comprising means of recursive calculation of a theoretical emission time for each cell pertaining to a virtual connection on the basis of parameters including at least the time of arrival of said cell and a spacing interval allotted to said connection;
spacing control means for managing the cell memory, with the aid of an associated pointer memory, in such a way that the cell memory comprises, for each virtual connection for which it contains cells, a list of locations where said cells are stored in first-in first-out mode between a start of list and an end of list; and
sorting means for ordering data elements, each comprising a virtual connection identity and a sort key consisting of the theoretical time of emission of the cell contained in the start of list relating to said virtual connection, and for selecting at least one data element having a minimum sort key, the spacing control means being devised so as to command the emission of a cell contained in the start of list relating to a virtual connection identified in a data element selected by the sorting means.
Upon the arrival of a cell pertaining to a virtual connection for which the cell memory contains no cell, the sorting means receive a new data element comprising the identity of said virtual connection and, as sort key, the theoretical time of emission of said cell supplied by the means of recursive calculation. Upon the emission of a first cell pertaining to a virtual connection for which the cell memory comprises a list of locations further containing at least one second cell, the sorting means receive a new data element comprising the identity of said virtual connection and, as sort key, a theoretical time of emission of said second cell equal to the theoretical time of emission of said first cell plus the spacing interval allotted to said connection.
There is a saving in the complexity of the spacer and a gain in its flexibility of use through the fact that the cells emitted are chosen by a sorting procedure based on the starts of list per connection rather than on all the cells stored.
The mode of determining the emission times limits the delays suffered by the cells owing to the conflicts with regard to the emission slots. In certain cases, even the delay suffered relative to the theoretical emission times obtained by the means of recursive calculation is reduced.
The sorting means advantageously comprise one or more binary-tree sorting devices of a type described in detail below.